package structures.sort;

import java.util.Arrays;

// 归并排序
public class MergeSortDemo {

    private static final int LENGTH = 80000;

    public static void main(String[] args) {
        // 生成数据
        int[] data = new int[LENGTH];
        for (int index = 0; index < data.length; index++) {
            data[index] = (int) (Math.random() * LENGTH);
        }

        // 打印数据
        System.out.println(Arrays.toString(data));

        long startTime = System.currentTimeMillis();
        mergeSort(data, 0, data.length - 1);
        System.out.println("----------------消耗时间: " + (System.currentTimeMillis() - startTime) + " ms------------");

        // 打印数据
        System.out.println(Arrays.toString(data));
    }


    private static void mergeSort(int[] data, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(data, left, mid);
            mergeSort(data, mid + 1, right);
            merge(data, left, mid, right);
        }
    }

    /**
     * 合并的方法
     * @param data  原始数组
     * @param left  左边的有序序列的初始索引
     * @param mid   中间的索引值
     * @param right 右边的索引值
     */
    private static void merge(int[] data, int left, int mid, int right) {
//        System.out.println("----" + left + "----" + mid + "----" + right + "----");
        int i = left;   // 左边有序序列的初始索引
        int j = mid + 1;    // 右边有序序列的初始索引
        int t = 0;  // 指向temp的索引
        int[] temp = new int[right - left + 1];
        // 1、 把左右两边的(有序)数据合并到temp数组中,直到有一方全部处理完毕
        while (i <= mid && j <= right) {
            if (data[i] <= data[j]) {
                temp[t++] = data[i++];
            } else {
                temp[t++] = data[j++];
            }
        }

        // 2、处理另一方没有处理完的数据
        while (i <= mid) {
            temp[t++] = data[i++];
        }
        while (j <= right) {
            temp[t++] = data[j++];
        }

        // 3、将temp中的数据复制到原始数组中
        for (int index = 0; index < temp.length; index++) {
            data[left + index] = temp[index];
        }
    }
}
